"""
将这个问题转换成图的问题
"""

import math
"""
65.31%
8.22%
"""
class Solution:
    
    def numSquares(self, n: int) -> int:
        queue = []
        queue.append((n, 0))
        visited = [False] * (n+1)
        visited[n] = True
        while queue:
            num, step = queue.pop()

            i = 1
            while num - i * i >= 0:
                # 这里不添加重复的节点，因为后面添加的节点肯定没有前面的短。
                tmp = num - i * i
                if tmp < 0:
                    break
                if tmp == 0:
                    return step + 1 
                if not visited[tmp]:
                    # 这里一定要插在最前面，不然就是成深度遍历了
                    queue.insert(0, (tmp, step+1))
                    visited[tmp] = True
                i += 1


if __name__ == "__main__":
    r = Solution().numSquares(12)
    print("r=", r)

